package labuladong.BFS.打开转盘锁;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        String[] deadends = {"0201","0101","0102","1212","2002"};
        String target = "0202";
        int step = bfs(deadends, target);
        System.out.println(step);
    }

    public static String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9')
            ch[j] = '0';
        else
            ch[j] += 1;
        return String.valueOf(ch);
    }

    public static String minusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0')
            ch[j] = '9';
        else
            ch[j] -= 1;
        return String.valueOf(ch);
    }

    public static int bfs (String[] deadends, String target) {
        HashSet<String> deads = new HashSet<>();
        // 将deadends添加进deads集合内
        for(String s : deadends)
            deads.add(s);
        // 记录已经穷举过得密码
        HashSet<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        // 从起点开始启动⼴度优先搜索
        int step = 0;
        queue.offer("0000");
        visited.add("0000");

        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int i=0; i<size; i++){
                String curr = queue.poll();
                // 判断是否符合条件
                if(deads.contains(curr))
                    continue;
                if (target.equals(curr))
                    return step;

                for(int j=0; j<4; j++){
                    String up = plusOne(curr, j);
                    if(!visited.contains(up)){
                        queue.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(curr, j);
                    if(!visited.contains(down)){
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            // 在这里增加步数
            step++;
        }
        // 没有桥穷举到目标密码返回-1
        return -1;
    }
}
